Sprawy organizacyjne

• Formuła zajęć: Wykład koleżeński, dyskusja;
• Forma prezentacji: Omówienie wykładu/tematu pojawiającego się na kursie: http://cs229.stanford.edu/;
• Forma prezentacji dowolna (proponuję trochę omówienia teoretycznego + przykłady metod w kodzie, wizualizacja);
• Jak często prezentujemy - co tydzień;
• Chętni mogą wrzucać swoje prezentacje do repo: https://github.com/lukaszlaszczuk/ml-gauss-summer-2021 ;
• Skupiamy się na metodach, a nie na narzędziach;
• Pytania, sugestie?

Rozkład zajęć

1. Intro to ML, Linear Regression and Gradient Descent;
2. Locally Weighted & Logistic Regression;
3. Perceptron & Generalized Linear Model;
4. GDA & Naive Bayes;
5. Support Vector Machines;
6. Kernels;
7. Data Splits, Models & Cross-Validation;
8. Approx/Estimation Error & ERM;

9. Decision Trees and Ensemble Methods;
10. Introduction to Neural Networks
11. Backprop & Improving Neural Networks
12. Debugging ML Models and Error Analysis
13. Expectation-Maximization Algorithms
14. Factor Analysis
15. Independent Component Analysis & RL
16. MDPs & Value/Policy Iteration
17. Continuous State MDP & Model Simulation
18. Reward Model & Linear Dynamical System
19. RL Debugging and Diagnostics.

Plan na dziś

• wstęp do uczenia maszynowego;
• regresja liniowa;
• gradient descent (metoda gradientu prostego, stochastyczny gradient prosty, minibatch gradient descent);

Co to jest uczenie maszynowe?

• Arthur Samuel (1959) - "dziedzina nauki, która umożliwia uczenie komputerów bez konieczności ich programowania";
• Tom M. Mitchell - "Mówimy, że program komputerowy uczy się ze skutecznością S zadania Z na podstawie doświadczenia D, jeśli jego skuteczność w wykonywaniu zadania Z rośnie wraz ze wzrostem doświadczenia D."

Interpretacja definicji Mitchella

Istotne aspekty przy realizowaniu projektu/zadania uczenia maszynowego:

• Odpowiednie rozpoznanie zadania Z, tj. zrozumienie problemu biznesowego, infrastruktury/bazy danych klienta, odbiorcy końcowego, ... Czy uczenie maszynowe jest w ogóle potrzebne? rules of ml;
• Zebranie odpowiedniego "doświadczenia" D, tj. danych. Integracja z infrastrukturą klienta czyszczenie danych, wizualizacja, transformacje danych, .... Jednym słowem wszystko, co może pozwolić na zwiększenie skuteczności (może stanowić najdłuższą część projektu);
• Określenie sposobu mierzenia skuteczności S, np. dokładność, błąd średniokwadratowy, miara F1, ...

Rodzaje uczenia maszynowego

• nadzorowane uczenie maszynowe (supervised ML);
• nienadzorowane uczenie maszynowe (unsupervised ML);
• uczenie maszynowe ze wzmocnieniem (reinforcement learning);
• semi-supervised ML

Nadzorowane uczenie maszynowe

Dane: $(X, y)$, gdzie $X$ to zmienne wyjaśniające a $y$ to zmienna wyjaśniana;

Cel: Znaleźć optymalną funkcję przekształcającą $X$ w $y$.

• Dwa typy problemów: regresja (gdy zmienna wyjaśniana jest ciągła), klasyfikacja (gdy zmienna wyjaśniana jest dyskretna);

• Typy klasyfikacji: binarna (binary), wieloklasowa (multiclass), wieloetykietowa (multi-label). Przykłady?

Nienadzorowane uczenie maszynowe

Dane: $X$ - zbiór danych bez zmiennej wyjaśnianej;

Cel: Znaleźć "ciekawą" strukturę w danych.

Przykłady?

• segmentacja rynku;
• klastrowanie DNA;
• systemy rekomendacyjne;
• topic modeling;
• detekcja anomalii;
• social network analysis;
• szukanie zmiany trendu.

Uczenie maszynowe ze wzmocnieniem

• osadzamy "agenta" w pewnym otoczeniu i pozwalamy mu eksperymentować;
• nagradzamy go za działania pozytywne oraz karzemy za działania negatywne w taki sposób, aby agent nauczył się wykonywać określone działania.

Przykłady?

Use-cases link

• granie w gry (komputerowe, szachy, go);
• autonomiczne samochody;
• boty tradingowe;
• optymalizacja zużycia energii (Google Data Center);
• chatboty.

Semi-supervised learning

• Używany w przypadku, gdy mamy ograniczony dostęp do wartości zmiennej wyjaśnianej;
• Dzięki tego typu metodom możemy generować dane (zdjęcia, filmy, muzyka, ...) przykład

Regresja liniowa

Typowy przykład:

• Estymacja ceny mieszkania na podstawie jego metrażu

Schemat / Terminologia

• Szukamy funkcji (hipotezy) $h$ minimalizującą pewną funkcję straty. Dla regresji liniowej $h(x) = \theta_0+\theta_1 x$.
• $\theta$ - szukane parametry, minimalizujące pewną funkcję straty $J$;
• $x$ - zmienne wyjaśniające;
• $y$ - zmienna wyjaśniana;
• $(x^{(i)},y^{(i)})$ - $i$-ta obserwacja ze zbioru treningowego.
• $m$ - liczba obserwacji w zbiorze (rzędów);
• $n$ - liczba zmiennych wyjaśniających (kolumn);
• $J(\theta) = \displaystyle\frac{1}{2m}\sum_{i=1}^{m}\left(h(x^{(i)})-y^{(i)}\right)^2$

Metoda gradientu prostego

• algorytm szukania minimów lokalnych funkcji (straty);
• ma zastosowanie dla szerokiej gamy problemów;
• istnieje kilka odmian algorytmu: wsadowa (batchowa), stochastyczna, minibatchowa.

Kroki algorytmu (wsadowy/batch gradient prosty)

1. Wybierz początkowe $\theta$ (np. $\theta = \vec{0}$).
2. Modyfikuj $\theta$, aby zminimalizować $J(\theta)$.
3. $\theta_j:=\theta_j - \alpha\, \cfrac{\partial}{\partial \theta_j}\, J(\theta)$, gdzie $\alpha$ to współczynnik uczenia (learning rate), np. $\cfrac{\partial}{\partial \theta_j}\, J(\theta) = \cfrac{\partial}{\partial \theta_j}\cfrac{1}{2m}\displaystyle\sum_{i=1}^{m}\left(h_{\theta}(x^{(i)})-y^{(i)}\right)^2 = \ldots = \cfrac{1}{m}\displaystyle\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$.
   Macierzowo możemy zapisać: $\cfrac{\partial}{\partial \theta_j}\, J(\theta) = \cfrac{1}{m} X^T \,(X\theta -y)$.
4. Zaktualizuj $\theta_j$: $\theta_j:=\theta_j-\alpha \, \cfrac{1}{m}\displaystyle\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$.
   Macierzowo: $\theta := \theta - \alpha \, \cfrac{1}{m}\,X^T \,(X\theta -y)$
5. Powtarzaj kroki 1.-4. do momentu, aż błąd będzie wystarczająco niski lub osiągniemy maksymalny krok.

Implementacja

def loss_function(y_pred, y_real):
    return 1/2 * np.mean((y_pred-y_real)**2)

def batch_gradient_descent(theta,
                           X,
                           y,
                           n_iteration,
                           alpha,
                           theta_snapshot_rate=None):
    
    theta_snapshot_list = [[copy.deepcopy(theta), 0]]
    for iteration in range(n_iteration):
        theta = copy.deepcopy(theta)
        if iteration % theta_snapshot_rate == 0 and iteration!=0:
            append_list = [theta, iteration]
            theta_snapshot_list.append(append_list)
            
        gradient = np.mean(X.T.dot(X.dot(theta) - y), axis=1)
        gradient = np.reshape(gradient, (-1, 1))
        theta -= alpha * gradient     
        
    if len(theta_snapshot_list) > 0:
        return theta, theta_snapshot_list
    else:
        return theta

Przykłady: $\alpha=10^{-10}$

PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)

Przykłady: $\alpha=10^{-9}$

PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, -1000000, 10000000)

Przykłady: $\alpha=2\cdot10^{-15}$

PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)

Kroki algorytmu (stochastyczny gradient prosty):

• stosowany w przypadku, kiedy mamy duże dane i batchowy gradient descent jest wolny:

1. Wybierz początkowe $\theta$ (np. $\theta = \vec{0}$).
2. for i in range(m):
3. Modyfikuj $\theta$, aby zminimalizować $J(\theta)$.
4. Wybierz losową obserwację ze zbioru danych $(x^{(i)}, y^{(i)})$;
5. $\theta_j:=\theta_j-\alpha \, (h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$;
6. Za $\alpha$ można przyjąć: $\cfrac{t_0}{(t+t_1)}$, gdzie $t_0$ i $t_1$ to wybrane współczynniki, a $t$ to number iteracji.
7. Powtarzaj 2. - 6. ustaloną liczbę razy.

def learning_schedule(t, t0, t1):
    return t0/(t+t1)

def stoch_gradient_descent(theta,
                           X,
                           y,
                           n_iteration,
                           alpha=None,
                           learning_schedule=None,
                           t0=None,
                           t1=None,
                           theta_snapshot_rate=None):
    
    theta_snapshot_list = [[copy.deepcopy(theta), 0]]
    for iteration in range(n_iteration):
        theta = copy.deepcopy(theta)
        if iteration % theta_snapshot_rate == 0 and iteration != 0:
            append_list = [theta, iteration]
            theta_snapshot_list.append(append_list)
            
        for i in range(len(X)):
            rand_idx = np.random.randint(len(X))
            xi = X_b[rand_idx:rand_idx+1]
            yi = y[rand_idx:rand_idx+1]
            gradient = xi.T.dot(xi.dot(theta) - yi)
            if learning_schedule:
                alpha = learning_schedule(iteration*len(X)+i, t0, t1)
            theta -= alpha*gradient
        
    if len(theta_snapshot_list) > 0:
        return theta, theta_snapshot_list
    else:
        return theta

Przykłady:

n_iteration = 101
t0, t1 = 5, 5*10**8
theta_0 = np.zeros((2,1))
thetas_end, thetas_snapshot = stoch_gradient_descent(theta_0,
                                                    X_b,
                                                    y,
                                                    n_iteration,
                                                    learning_schedule=learning_schedule,
                                                    t0=t0,
                                                    t1=t1,
                                                    theta_snapshot_rate=1)

PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, (t0, t1), 0, 6000, 0, 1000000, "t0, t1:")

n_iteration = 101
alpha = 10**-10
theta_0 = np.zeros((2,1))
thetas_end, thetas_snapshot = stoch_gradient_descent(theta_0,
                                                    X_b,
                                                    y,
                                                    n_iteration,
                                                    alpha=alpha,
                                                    theta_snapshot_rate=1)

PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)